package 动态规划.组合求和系列;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author aodre , QQ : 480029069
 * @date 2022/12/27 9:19
 */
public class leetcode494目标和 {


    /*
    ①：
            if(rest == 0){
            return 1;
        }
       if（index == nums.length ）{
            return 0;
       }


      ②：

        if(index == nums.length){
            return rest == 0 ? 1: 0;
        }

        上面的阿区别， 主要是集合数据量的关系！
        ①： 只要 rest == 0 就不用往后 走了， 这种情况其实是因为数据都是 正数， 所以 再递归下去也没有任何的意义！

        ②：index 走到 len 的时候，判断一下， rest 满不满足 ， 这个其实 正统的写法， 只不过
        ①在此 数据 范围的基础上， 进行了一些的优化！ 要明白本质是什么！
     */



    /*
     https://leetcode.cn/problems/target-sum/solutions/816711/gong-shui-san-xie-yi-ti-si-jie-dfs-ji-yi-et5b/
     宫水三叶的题解：  主要是里面的  这一部分的代码， 用map 进行缓存的一个代码！

      https://www.programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html#%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95
      卡尔的 题解 就直接是 最优解
     */



    /*
    简单题
    改一下 dp 和 记忆化搜索就可以了！
     */

    public int recursion(int index, int rest, int len, int nums[]) {
        if (index == len)
            return rest == 0 ? 1 : 0;
        int ans = 0;
        ans = recursion(index + 1, rest - nums[index], len, nums);
        ans += recursion(index + 1, rest + nums[index], len, nums);
        return ans;
    }


    /*
     有点小  低估这个题了！  这个题 其实也给 一种另外的思路， 只要能缓存 到 已经走过的记录 就行
     用 map 可能会 map  里面 套 map  或者 用 数组 来做这件事 都是可以的

     */
    public int findTargetSumWays(int[] nums, int target) {
        Map<Integer, Map<Integer, Integer>> dp = new HashMap<>();
        return recursion(0, nums, target, dp);
    }

    public int recursion(int index, int nums[], int rest, Map<Integer, Map<Integer, Integer>> dp) {
        if (index == nums.length) {
            return rest == 0 ? 1 : 0;
        }
        Map<Integer, Integer> map = dp.get(index);
        if (map != null && dp.get(index).containsKey(rest)) {
            return dp.get(index).get(rest);
        }
        int ans = 0;
        // positive
        ans = recursion(index + 1, nums, rest + nums[index], dp);
        // negative
        ans += recursion(index + 1, nums, rest - nums[index], dp);
        if (map == null) {
            map = new HashMap<>();
        }
        map.put(rest, ans);
        dp.put(index, map);
        return ans;
    }

    /*
     卡尔的 题解
     */
    public int function(int nums[], int target) {
        int sum = Arrays.stream(nums).sum();
        if ((sum + target & 1) != 0 || sum < Math.abs(target)) {
            return 0;
        }
        int rest = sum + target >> 1;
        return function2(0, rest, nums);
    }

    public int function2(int index, int rest, int nums[]) {
//        if(rest == 0){
//            return 1;
//        }
        if (index == nums.length) {
            return rest == 0 ? 1 : 0;
        }
        int ans = function2(index + 1, rest - nums[index], nums);
        ans += function2(index + 1, rest, nums);
        return ans;
    }

    public static void main(String[] args) {

    }

}
